import java.util.Arrays;

public class Makesquare {

    int[] nums = new int[4];
    public boolean makesquare(int[] matchsticks) {
        int sum = Arrays.stream(matchsticks).sum();
        if (sum % 4 != 0) return false;
        Arrays.sort(matchsticks);
        int l = 0;
        int r = matchsticks.length - 1;
        while (l <= r) {
            int temp = matchsticks[l];
            matchsticks[l] = matchsticks[r];
            matchsticks[r] = temp;
            ++l;
            --r;
        }
        return process(matchsticks, sum / 4, 0);
    }

    public boolean process(int[] matchsticks, int target, int i) {
        if (i == matchsticks.length) {
            return true;
        }
        for (int j = 0; j < nums.length; j++) {
            if (matchsticks[i] + nums[j] <= target) {
                nums[j] += matchsticks[i];
                if (process(matchsticks, target, i + 1)) return true;
                nums[j] -= matchsticks[i];
                if (nums[j] == 0 || matchsticks[i] + nums[j] == target) break;
            }
        }
        return false;
    }
}
